package codeRandomThoughts.Test76最小覆盖子串;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Solution {
    public static String minWindow(String s, String t) {
        if (t.length() > s.length()) return "";
        //首先用一个哈希表保存t中每个字母出现了几次
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        }

        //滑动窗口左右边界
        int left = 0;
        int right = 0;

        //返回值
        int minLeft = -1;
        int minRight = -1;
        int minLen = Integer.MAX_VALUE;

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (hashMap.containsKey(rightChar)) {
                hashMap.put(rightChar, hashMap.get(rightChar) - 1);
            }

            if (isValid(hashMap)) {
                while (isValid(hashMap)) {
                    int len = right - left + 1;
                    if (len < minLen) {
                        minLen = len;
                        minLeft = left;
                        minRight = right;
                    }
                    //去除left
                    char leftChar = s.charAt(left);
                    if (hashMap.containsKey(leftChar)) {
                        hashMap.put(leftChar, hashMap.get(leftChar) + 1);
                    }
                    left++;
                }
            }

            right++;
        }

        return minLeft==-1?"":s.substring(minLeft, minRight + 1);
    }

    private static boolean isValid(HashMap<Character, Integer> hashMap) {
        Set<Map.Entry<Character, Integer>> entries = hashMap.entrySet();
        for (Map.Entry<Character, Integer> entry : entries) {
            if (entry.getValue() > 0) {
                return false;
            }
        }
        return true;
    }


}
